package algocasts;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class P124_CourseSchedule {
    private boolean hasCycle(List<List<Integer>> graph, boolean[] visited,
                             boolean[] checked, int v) {
        if (visited[v]) return true;
        visited[v] = true;
        for (Integer i : graph.get(v)) {
            if (!checked[i] && hasCycle(graph, visited, checked, i))
                return true;
        }
        checked[v] = true;
        visited[v] = false;
        return false;
    }

    // Time: O(V+E)  Space: O(V+E)
    public boolean canFinish_DFS(int n, int[][] pairs) {
        if (n <= 1 || pairs == null || pairs.length == 0) return true;
        List<List<Integer>> graph = new ArrayList<>(n);
        for (int i = 0; i < n; i++)
            graph.add(new ArrayList<>());
        for (int[] pair : pairs) {
            graph.get(pair[1]).add(pair[0]);
        }

        boolean[] checked = new boolean[n];
        boolean[] visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            if (!checked[i] && hasCycle(graph, visited, checked, i))
                return false;
        }
        return true;
    }

    public boolean canFinish_TopoSortAdjList(int n, int[][] pairs) {
        if (n <= 1 || pairs == null || pairs.length == 0) return true;
        int[] inDegree = new int[n];
        List<List<Integer>> graph = new ArrayList<>(n);
        for (int i = 0; i < n; i++)
            graph.add(new ArrayList<>());

        for (int[] pair : pairs) {
            graph.get(pair[1]).add(pair[0]);
            ++inDegree[pair[0]];
        }

        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < inDegree.length; i++)
            if (inDegree[i] == 0) q.add(i);

        int count = 0;
        while (!q.isEmpty()) {
            int v = q.poll();
            ++count;
            for (Integer i : graph.get(v)) {
                --inDegree[i];
                if (inDegree[i] == 0) q.add(i);
            }
        }
        return count == n;
    }


}
